//反转链表

//方法一：迭代法
//1.迭代需要三个指针：pre指向空节点，cur指向头结点head，next指向head->next
//因为head->next可能不存在，next在循环中定义，这样如果head为空就不会进入循环
//2.迭代过程: next指向cur->next
//          cur->next指向pre
//          pre移动到cur位置
//          cur移动到nxt位置
//3.当cur为空时，返回pre


struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x);
};
class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            ListNode* pre = NULL;
            ListNode* cur = head;
            while(cur != NULL)
            {
                ListNode* next = cur->next;
                cur->next = pre;
                pre = cur;
                cur= next;

            }
            return pre;
        }
};

//方法二：递归
class Solution {
    public:
        ListNode* reverse(ListNode* pre, ListNode*cur)
        {
            if(cur == NULL) return pre;
            ListNode* next = cur->next;
            cur->next = pre;
            return reverse(cur, next);

        }

        ListNode* reverseList(ListNode* head)
        {
            return reverse(NULL, head);
        }
};
